Problema de satisfacibilidad booleana

Mira otros diccionarios:

• Problema de satisfacibilidad booleana — Saltar a navegación, búsqueda En teoría de la complejidad computacional, el Problema de satisfacibilidad booleana (SAT) fue el primer problema identificado como perteneciente a la clase de complejidad NP completo. Se trata de un problema donde… …   Wikipedia Español

• NP-completo — En teoría de la complejidad computacional, la clase de complejidad NP completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP completo. Se puede decir que los… …   Wikipedia Español

• Lista de 21 problemas NP-completos de Karp — Por Lista de 21 problemas NP completos de Karp se entiende a una lista de 21 problemas computacionales famosos, que tratan sobre combinatoria y teoría de grafos, y que cumplen la característica en común de que todos ellos pertenecen a la clase de …   Wikipedia Español

• Teorema de Cook — En teoría de la complejidad computacional, el Teorema de Cook establece lo siguiente: El Problema de satisfacibilidad booleana (SAT) es NP completo. Stephen Cook (1971) Cook demostró este teorema en su artículo de 1971 The Complexity of Theorem… …   Wikipedia Español

• NP (Complejidad computacional) — Saltar a navegación, búsqueda Los recursos comúnmente estudiados en complejidad computacional son: – El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver un problema. – El espacio: mediante… …   Wikipedia Español

• NP (clase de complejidad) — En teoría de la complejidad computacional, NP es el acrónimo en inglés de nondeterministic polynomial time ( tiempo polinomial no determinista ). Es el conjunto de problemas que pueden ser resueltos en tiempo polinómico por una máquina de Turing… …   Wikipedia Español

• Computación basada en ADN — La Computación basada en ADN consiste en usar moléculas de ADN en vez de procesadores basados en silicio. Las ventajas de la computación por ADN se basan en dos características fundamentales: El gran paralelismo de las hebras de ADN. Muchos de… …   Wikipedia Español

• Hilary Putnam — Retrato de Putnam. Hilary Whitehall Putnam (nacido el 31 de julio de 1926, en Chicago (Illinois)) es u …   Wikipedia Español

• Clases de complejidad P y NP — Diagrama de clases de complejidad para el caso en que P ≠ NP. La existencia de problemas fuera tanto de P como de NP completos en este caso fue determinada por Ladner.[1] La relación entre las clases de complejidad P …   Wikipedia Español

• Numeral-P — En teoría de la complejidad computacional, la clase de complejidad #P (pronunciado numeral P) es el conjunto de los problemas de conteo asociados a los problemas de decisión en el conjunto NP. Un problema en NP se describe usualmente con la… …   Wikipedia Español